#include <stdio.h>
#include "msTree.h"

void tranTree(TNode* root)
{
	if(root==0)
		return;
	TNode* lch=root->lch;
	TNode* rch=root->rch;
	tranTree(lch);
	tranTree(rch);
	root->lch=rch;
	root->rch=lch;
}
void swap(TNode* node)
{
	if(node!=0)
	{
		TNode* tmp=node->lch;
		node->lch=node->rch;
		node->rch=tmp;
	}
}
void tranTree2(TNode* root)
{
	if(root!=0)
	{
		TNode* st[20];
		int top=-1;
		
		st[++top]=root;
		while(top!=-1)
		{
			TNode* tmp=st[top--];
			if(tmp->rch!=0)
			{
				st[++top]=tmp->rch;
			}
			if(tmp->lch!=0)
			{
				st[++top]=tmp->lch;
			}
			swap(tmp);
			//printf("%d ",tmp->data);
		}
	}
}
void printLev(TNode* root)
{
	const int SIZE=20;
	TNode* qu[SIZE];
	int head=0,tail=0;
	
	if(root!=0)
	{
		qu[++tail]=root;
		while(head!=tail)
		{
			TNode* tmp=qu[++head%SIZE];
			if(tmp->lch!=0)
			{
				qu[++tail]=tmp->lch;
			}
			if(tmp->rch!=0)
			{
				qu[++tail]=tmp->rch;
			}
			printf("%d ",tmp->data);
		}
		printf("\n");
	}
}
int main()
{
	int pre[]={1,2,3,4,5,6,7};
	int in[]={2,3,1,5,4,7,6};
	TNode* root=createTree(pre,in,7);
	printTree(root);
	printf("\n");
	tranTree2(root);
	printTree(root);
	printf("\n");
	printLev(root);
	
	return 0;
}
